/*
 * @Author: 生俊甫 1758142861@qq.com
 * @Date: 2024-10-13 11:06:31
 * @LastEditors: 生俊甫 1758142861@qq.com
 * @LastEditTime: 2024-10-15 20:16:27
 * @FilePath: /sjf/2024-project/2024_centos/test_to_c/union_find_set/union_find.hh
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#pragma once
#include <iostream>
#include <vector>

/**
 * 并查集
 */
//template<class T>
class union_find_set
{
public:
    //初始化
    union_find_set(int n)
    :_ufs(n,-1)
    {}
    ~union_find_set()
    {}
    //查找元素所在集合
    // int find_root(int x)
    // {
    //     int parent = x;
    //     while(_ufs[parent] >= 0)
    //     {
    //         parent = _ufs[parent];
    //     }
    //     return parent;
    //     //递归实现
    //     return _ufs[x] >= 0 ? find_root(_ufs[x]) : x;
    // }
    int find_root(int x)
    {
        //找到该集合中的根节点
        int root = x;
        while(_ufs[root] >= 0)
        {
            root = _ufs[root];
        }
        /**
         * 路径压缩,将该路径下的所有节点直接和根节点相连接
         * 也就是将多层结构，压缩到了一层，让每一个子节点直接和根节点直接连接
         *           2             压缩           2
         *        3    4          ---->     3 4 5 6 7 8 9
         *      5  6  7   8
         */
        while(_ufs[x] >= 0)
        {
            int parents = _ufs[x];
            _ufs[x] = root;
            x = parents;
        }
        return root;
    }
    //判断两个元素是否在一个集合中
    bool in_same_set(int a,int b)
    {
        return find_root(a) == find_root(b);
    }
    //合并两个元素所在的集合
    bool union_set(int a,int b)
    {
        // 先获取到两个元素的根节点
        int parent1 = find_root(a);
        int parent2 = find_root(b);
        //如果两个已经属于同一根节点了就退出即可
        if (parent1 == parent2)
            return false;
        /**
         * 开始合并(是将小集合合并到大集合上)
         * 2是大集合时，交换，永远让1表示大集合
         */
        if(_ufs[parent1] > _ufs[parent2])
            std::swap(parent1,parent2);
        //重新统计合并后的集合元素
        _ufs[parent1] += _ufs[parent2];
        //将小集合根节点内的值指向大节点的根节点
        _ufs[parent2] = parent1;
        return true;
    }
    //获取并查集中集合的个数
    int get_num()
    {
        int count = 0;
        for(const int& val : _ufs)
        {
            if(val < 0)
                count++;
        }
        return count;
    }
private:
    std::vector<int> _ufs;
};